package com.leetcode.partition10;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/10/22 11:59
 */
public class LC986区间列表的交集 {

    public static int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        return doublePointer(firstList, secondList);
    }

    public static void main(String[] args) {
        int[][] firstList = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
        int[][] secondList = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};
//        int[][] firstList = {{8, 15}};
//        int[][] secondList = {{2, 6}, {8, 10}, {12, 20}};
        Arrays.stream(intervalIntersection(firstList, secondList)).forEach(val -> System.out.println(Arrays.toString(val)));
    }

    private static int[][] doublePointer(int[][] firstList, int[][] secondList) {
        List<int[]> answers = new ArrayList<>();
        int i = 0, j = 0;
        while (i < firstList.length && j < secondList.length) {
            int[] first = firstList[i], second = secondList[j];
            int start = Math.max(first[0], second[0]);
            int end = Math.min(first[1], second[1]);
            if (start <= end) answers.add(new int[]{start, end});

            if (second[1] < first[1]) {
                j++;
            } else if (second[1] > first[1]) {
                i++;
            } else {
                i++;
                j++;
            }
        }
        return answers.toArray(new int[answers.size()][]);
    }
}
